package com.study.lihan.letcode.offer;

import java.util.Arrays;
import java.util.List;

/**
 * @Author: lihan
 * @Date : 2022/9/22- 09
 * @DESCRIPTION: 题目：输入一个非负数n，请计算0到n之间每个数字的二进制形式中1的个数，并输出一个数组。
 * 例如，输入的n为4，由于0、1、2、3、4的二进制形式中1的个数分别为0、1、1、2、1，因此输出数组[0，1，1，2，1]。
 * @version: 1.0
 */
public class T3 {
    public static void main(String[] args) {
        int n = 2;
        System.out.println(getResult(5));
    }
    public static int[] getResult (int n){
        int[] result = new int[n+1];
        if (n == 0){
            return result;
        }
        result[1] =1;
        if (n == 1){
            return result;
        }
        result[2] = 1;
        if (n == 2){
            return result;
        }
        for (int i = 3; i <=n ; i++) {
            int ceil = getCeil(n);
            if (ceil == i){
                result[i] =1;
            }else {
                result[i] = 1 + result[i - ceil];
            }


        }

        return result;
    }

    public static int getCeil (int n){
         n = n | (n >>1);
         n = n | (n >>2);
         n = n | (n >>4);
         n = n | (n >>8);
         n = n | (n >>16);
         n = (n +1)>>1;
        return n;
    }
}
